from typing import List


class Solution:
    """
    方法：动态规划，从三角形底部向上计算最小路径和
    
    Args:
        triangle: List[List[int]], 给定的三角形数组
        
    Returns:
        int, 从顶部到底部的最小路径和
        
    Time: O(n^2), n为三角形的行数
    
    Space: O(n), 使用一维dp数组存储中间结果
    """
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        n = len(triangle)
        dp = [0] * (n + 1)
        for i in range(n - 1, -1, -1):
            for j in range(len(triangle[i])):
                # 状态转移方程：取下一层相邻两个位置的最小值 + 当前值
                dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j]
        return dp[0]
        